package com.uyong.study.algorithm.sort;

import java.util.Arrays;

/**
 * 基数排序O(n),非原地O(n)，稳定
 * 
 * @author gonggy
 * @since 2019-01-30
 */
public class RadixSort implements ISort {

	@Override
	public void sort(int[] data) {
		if (data.length <= 1) {
			return;
		}
		// 确定最大数字，用于确定最大位数
		int max = Arrays.stream(data).max().getAsInt();

		// 计算最大数字的位数
		int maxBit = String.valueOf(max).length();

		// 从个位，十位，百位...循环排序
		for (int radix = 1; radix <= maxBit; radix++) {
			countingSort(data, radix);
		}
	}

	/**
	 * 计数排序
	 * 
	 * @param data
	 * @param radix 哪一位
	 */
	private void countingSort(int[] data, int radix) {
		// 1.申请一个计数数组，因为每位上的数字范围为0-9，所以计数数组大小固定为10
		int[] count = new int[10];

		// 2.统计该位的数字出现的次数
		for (int element : data) {
			count[getDigit(element, radix)]++;
		}

		// 3.累加计数数组，每一项为当前项和前面各项的和
		for (int i = 1; i < count.length; i++) {
			count[i] += count[i - 1];
		}

		// 4.排序过程
		int[] sorted = new int[data.length];
		for (int i = data.length - 1; i >= 0; i--) {
			int value = data[i]; // 待排序的元素
			int digit = getDigit(value, radix); // 给定位上的数字
			int index = count[digit] - 1; // 计算出元素在有序数组中实际的下标
			sorted[index] = value; // 将元素放到有序数组中
			count[digit]--;
		}

		System.arraycopy(sorted, 0, data, 0, data.length);
	}

	/**
	 * 提取指定位数上的数字，不足位数时返回0
	 * 
	 * @param number
	 * @param radix  哪一位
	 * @return
	 */
	private int getDigit(int number, int radix) {
		String str = String.valueOf(number);
		return radix > str.length() ? 0 : Integer.valueOf(String.valueOf(str.charAt(str.length() - radix)));
	}

}
